package com.fr.lintcode;

import org.junit.Test;

public class Q228 {

    /**
     * @param head: the head of linked list.
     * @return: a middle node of the linked list
     */
    public ListNode middleNode(ListNode head) {
        // write your code here
    	if(head == null) {
    		return null;
    	}
    	ListNode low = head;
    	ListNode fast = head;
    	while(fast != null && fast.next != null) {
    		fast = fast.next.next;
    		if(fast != null) {
    			low = low.next;
    		}
    	}
    	return low;
    }

    @Test
    public void testMiddleNode() {
    	ListNode node = build(6);
    	System.out.println(middleNode(node).val);
    }
    
    private ListNode build(int size) {
    	ListNode head = null;
    	ListNode tmp = null;
    	for(int i = 1; i <= size; i++) {
    		ListNode node = new ListNode(i);
    		if(head == null) {
    			head = node;
    			tmp = node;
    		}else {
    			tmp.next = node;
    			tmp = node;
    		}
    	}
    	return head;
    }

}
